<!DOCTYPE html>
<html lang="zh">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 5.3.0">


  <link rel="apple-touch-icon" sizes="180x180" href="/yuwanzi.io/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/yuwanzi.io/images/favicon-32x32-next.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/yuwanzi.io/images/favicon-16x16-next.png">
  <link rel="mask-icon" href="/yuwanzi.io/images/logo.svg" color="#222">

<link rel="stylesheet" href="/yuwanzi.io/css/main.css">



<link rel="stylesheet" href="//cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free@5.15.1/css/all.min.css">
  <link rel="stylesheet" href="//cdn.jsdelivr.net/npm/animate.css@3.1.1/animate.min.css">

<script class="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"suyuhuan.gitee.io","root":"/yuwanzi.io/","images":"/yuwanzi.io/images","scheme":"Muse","version":"8.2.0","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12},"copycode":false,"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"Suche...","empty":"We didn't find any results for the search: ${query}","hits_time":"${hits} results found in ${time} ms","hits":"${hits} results found"}};
  </script>
<meta name="description" content="红黑二叉查找树是2-3查找树的简单表示方式,它的代码量并不大,并且保证了平衡性.阅读本文前需先了解 《Algorithms,4th Edition》读书笔记-2-3查找树  概述 红黑树是一种自平衡的二叉查找树,它的基本思想是用标准的二叉查找树(完全由2-节点构成)和一些额外的信息(替换3-节点)来表示2-3树. 可以说红黑树是2-3树的一种等同. 红黑树中的链接可以分为两种类型:   红链接">
<meta property="og:type" content="article">
<meta property="og:title" content="《Algorithms,4th Edition》读书笔记-红黑二叉查找树">
<meta property="og:url" content="https://suyuhuan.gitee.io/yuwanzi.io/2017/03/30/2017-3-30-red_black_binary_search_tree/index.html">
<meta property="og:site_name" content="玉丸子 | Blog">
<meta property="og:description" content="红黑二叉查找树是2-3查找树的简单表示方式,它的代码量并不大,并且保证了平衡性.阅读本文前需先了解 《Algorithms,4th Edition》读书笔记-2-3查找树  概述 红黑树是一种自平衡的二叉查找树,它的基本思想是用标准的二叉查找树(完全由2-节点构成)和一些额外的信息(替换3-节点)来表示2-3树. 可以说红黑树是2-3树的一种等同. 红黑树中的链接可以分为两种类型:   红链接">
<meta property="og:locale">
<meta property="og:image" content="http://algs4.cs.princeton.edu/33balanced/images/redblack-encoding.png">
<meta property="og:image" content="http://algs4.cs.princeton.edu/33balanced/images/redblack-1-1.png">
<meta property="og:image" content="http://algs4.cs.princeton.edu/33balanced/images/redblack-color.png">
<meta property="og:image" content="http://algs4.cs.princeton.edu/33balanced/images/redblack-left-rotate.png">
<meta property="og:image" content="http://algs4.cs.princeton.edu/33balanced/images/redblack-right-rotate.png">
<meta property="og:image" content="http://algs4.cs.princeton.edu/33balanced/images/color-flip.png">
<meta property="article:published_time" content="2017-03-30T10:00:00.000Z">
<meta property="article:modified_time" content="2020-11-07T00:58:17.000Z">
<meta property="article:author" content="玉丸子">
<meta property="article:tag" content="2017">
<meta property="article:tag" content="Algorithms">
<meta property="article:tag" content="Tree">
<meta property="article:tag" content="数据结构">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="http://algs4.cs.princeton.edu/33balanced/images/redblack-encoding.png">


<link rel="canonical" href="https://suyuhuan.gitee.io/yuwanzi.io/2017/03/30/2017-3-30-red_black_binary_search_tree/">


<script class="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true,
    lang   : 'zh'
  };
</script>
<title>《Algorithms,4th Edition》读书笔记-红黑二叉查找树 | 玉丸子 | Blog</title>
  




  <noscript>
  <style>
  body { margin-top: 2rem; }

  .use-motion .menu-item,
  .use-motion .sidebar,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header {
    visibility: visible;
  }

  .use-motion .header,
  .use-motion .site-brand-container .toggle,
  .use-motion .footer { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle,
  .use-motion .custom-logo-image {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line {
    transform: scaleX(1);
  }

  .search-pop-overlay, .sidebar-nav { display: none; }
  .sidebar-panel { display: block; }
  </style>
</noscript>

<link rel="alternate" href="/yuwanzi.io/atom.xml" title="玉丸子 | Blog" type="application/atom+xml">
</head>

<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
  <div class="headband"></div>

  <main class="main">
    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="Navigationsleiste an/ausschalten" role="button">
    </div>
  </div>

  <div class="site-meta">

    <a href="/yuwanzi.io/" class="brand" rel="start">
      <i class="logo-line"></i>
      <h1 class="site-title">玉丸子 | Blog</h1>
      <i class="logo-line"></i>
    </a>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
    </div>
  </div>
</div>







</div>
        
  
  <div class="toggle sidebar-toggle" role="button">
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
  </div>

  <aside class="sidebar">

    <div class="sidebar-inner sidebar-nav-active sidebar-toc-active">
      <ul class="sidebar-nav">
        <li class="sidebar-nav-toc">
          Inhaltsverzeichnis
        </li>
        <li class="sidebar-nav-overview">
          Übersicht
        </li>
      </ul>

      <div class="sidebar-panel-container">
        <!--noindex-->
        <div class="post-toc-wrap sidebar-panel">
            <div class="post-toc animated"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%A6%82%E8%BF%B0"><span class="nav-number">1.</span> <span class="nav-text">概述</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E7%BA%A2%E9%BB%91%E6%A0%91%E7%9A%84%E6%80%A7%E8%B4%A8"><span class="nav-number">2.</span> <span class="nav-text">红黑树的性质</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E4%B8%8E2-3%E6%A0%91%E7%9A%84%E5%AF%B9%E5%BA%94%E5%85%B3%E7%B3%BB"><span class="nav-number">3.</span> <span class="nav-text">与2-3树的对应关系</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E8%8A%82%E7%82%B9%E7%9A%84%E5%AE%9E%E7%8E%B0"><span class="nav-number">4.</span> <span class="nav-text">节点的实现</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%97%8B%E8%BD%AC"><span class="nav-number">5.</span> <span class="nav-text">旋转</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E5%B7%A6%E6%97%8B%E8%BD%AC"><span class="nav-number">5.0.1.</span> <span class="nav-text">左旋转</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E5%8F%B3%E6%97%8B%E8%BD%AC"><span class="nav-number">5.0.2.</span> <span class="nav-text">右旋转</span></a></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E9%A2%9C%E8%89%B2%E8%BD%AC%E6%8D%A2"><span class="nav-number">6.</span> <span class="nav-text">颜色转换</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E6%A0%B9%E8%8A%82%E7%82%B9%E6%80%BB%E6%98%AF%E4%B8%BA%E9%BB%91"><span class="nav-number">6.0.1.</span> <span class="nav-text">根节点总是为黑</span></a></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%8F%92%E5%85%A5"><span class="nav-number">7.</span> <span class="nav-text">插入</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E5%90%91%E5%8D%95%E4%B8%AA2-%E8%8A%82%E7%82%B9%E4%B8%AD%E6%8F%92%E5%85%A5%E6%96%B0%E9%94%AE"><span class="nav-number">7.0.1.</span> <span class="nav-text">向单个2-节点中插入新键</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E5%90%91%E6%A0%91%E5%BA%95%E9%83%A8%E7%9A%842-%E8%8A%82%E7%82%B9%E6%8F%92%E5%85%A5%E6%96%B0%E9%94%AE"><span class="nav-number">7.0.2.</span> <span class="nav-text">向树底部的2-节点插入新键</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E5%90%91%E4%B8%80%E6%A3%B5%E5%8F%8C%E9%94%AE%E6%A0%91-%E4%B8%80%E4%B8%AA3-%E8%8A%82%E7%82%B9-%E4%B8%AD%E6%8F%92%E5%85%A5%E6%96%B0%E9%94%AE"><span class="nav-number">7.0.3.</span> <span class="nav-text">向一棵双键树(一个3-节点)中插入新键</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E5%B0%86%E7%BA%A2%E9%93%BE%E6%8E%A5%E5%90%91%E4%B8%8A%E4%BC%A0%E9%80%92"><span class="nav-number">7.0.4.</span> <span class="nav-text">将红链接向上传递</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E5%AE%9E%E7%8E%B0"><span class="nav-number">7.0.5.</span> <span class="nav-text">实现</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E6%80%BB%E7%BB%93"><span class="nav-number">7.0.6.</span> <span class="nav-text">总结</span></a></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%88%A0%E9%99%A4"><span class="nav-number">8.</span> <span class="nav-text">删除</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E8%87%AA%E9%A1%B6%E5%90%91%E4%B8%8B%E7%9A%842-3-4%E6%A0%91"><span class="nav-number">8.0.1.</span> <span class="nav-text">自顶向下的2-3-4树</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E5%88%A0%E9%99%A4%E6%9C%80%E5%B0%8F%E9%94%AE"><span class="nav-number">8.0.2.</span> <span class="nav-text">删除最小键</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-number">8.0.2.1.</span> <span class="nav-text">代码实现</span></a></li></ol></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E5%88%A0%E9%99%A4%E6%9C%80%E5%A4%A7%E9%94%AE"><span class="nav-number">8.0.3.</span> <span class="nav-text">删除最大键</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E5%88%A0%E9%99%A4%E6%93%8D%E4%BD%9C"><span class="nav-number">8.0.4.</span> <span class="nav-text">删除操作</span></a></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%80%BB%E7%BB%93-1"><span class="nav-number">9.</span> <span class="nav-text">总结</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#end"><span class="nav-number">10.</span> <span class="nav-text">end</span></a></li></ol></div>
        </div>
        <!--/noindex-->

        <div class="site-overview-wrap sidebar-panel">
          <div class="site-author site-overview-item animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
  <p class="site-author-name" itemprop="name">玉丸子</p>
  <div class="site-description" itemprop="description">这里是玉丸子的个人博客,与你一起发现更大的世界。</div>
</div>
<div class="site-state-wrap site-overview-item animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/yuwanzi.io/archives">
          <span class="site-state-item-count">68</span>
          <span class="site-state-item-name">Artikel</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
            <a href="/yuwanzi.io/categories/">
        <span class="site-state-item-count">39</span>
        <span class="site-state-item-name">Kategorien</span></a>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/yuwanzi.io/tags/">
        <span class="site-state-item-count">46</span>
        <span class="site-state-item-name">schlagwörter</span></a>
      </div>
  </nav>
</div>



        </div>
      </div>
    </div>
  </aside>
  <div class="sidebar-dimmer"></div>


    </header>

    
  <div class="back-to-top" role="button">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>

<noscript>
  <div class="noscript-warning">Theme NexT works best with JavaScript enabled</div>
</noscript>


    <div class="main-inner post posts-expand">


  


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="zh">
    <link itemprop="mainEntityOfPage" href="https://suyuhuan.gitee.io/yuwanzi.io/2017/03/30/2017-3-30-red_black_binary_search_tree/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/yuwanzi.io/images/avatar.gif">
      <meta itemprop="name" content="玉丸子">
      <meta itemprop="description" content="这里是玉丸子的个人博客,与你一起发现更大的世界。">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="玉丸子 | Blog">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          《Algorithms,4th Edition》读书笔记-红黑二叉查找树
        </h1>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">Veröffentlicht am</span>

      <time title="Erstellt: 2017-03-30 18:00:00" itemprop="dateCreated datePublished" datetime="2017-03-30T18:00:00+08:00">2017-03-30</time>
    </span>
      <span class="post-meta-item">
        <span class="post-meta-item-icon">
          <i class="far fa-calendar-check"></i>
        </span>
        <span class="post-meta-item-text">Bearbeitet am</span>
        <time title="Geändert am: 2020-11-07 08:58:17" itemprop="dateModified" datetime="2020-11-07T08:58:17+08:00">2020-11-07</time>
      </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">in</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/yuwanzi.io/categories/Algorithms/" itemprop="url" rel="index"><span itemprop="name">Algorithms</span></a>
        </span>
          . 
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/yuwanzi.io/categories/Algorithms/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" itemprop="url" rel="index"><span itemprop="name">数据结构</span></a>
        </span>
          . 
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/yuwanzi.io/categories/Algorithms/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Tree/" itemprop="url" rel="index"><span itemprop="name">Tree</span></a>
        </span>
    </span>

  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
        <blockquote>
<p><code>红黑二叉查找树</code>是<code>2-3查找树</code>的简单表示方式,它的代码量并不大,并且保证了平衡性.<br>阅读本文前需先了解 <a target="_blank" rel="noopener" href="http://sylvanassun.github.io/2017/03/28/2_3tree/">《Algorithms,4th Edition》读书笔记-2-3查找树</a></p>
</blockquote>
<h2 id="概述"><a href="#概述" class="headerlink" title="概述"></a>概述</h2><hr>
<p><code>红黑树</code>是一种自平衡的<code>二叉查找树</code>,它的基本思想是<strong>用标准的<code>二叉查找树</code>(完全由<code>2-节点</code>构成)和一些额外的信息(替换<code>3-节点</code>)来表示<code>2-3树</code>.</strong> 可以说<code>红黑树</code>是<code>2-3树</code>的一种等同.</p>
<p><code>红黑树</code>中的链接可以分为两种类型: </p>
<ul>
<li><strong>红链接</strong> : 它将两个<code>2-节点</code>连接起来构成一个<code>3-节点</code>(也可以说是将<code>3-节点</code>表示为由一条<strong>红色左链接</strong>(两个<code>2-节点</code>其中之一是另一个的左子节点)相连的两个<code>2-节点</code>).</li>
</ul>
<ul>
<li><strong>黑链接</strong> : 表示<code>2-3树</code>中的普通链接.</li>
</ul>
<p><img src="http://algs4.cs.princeton.edu/33balanced/images/redblack-encoding.png"></p>
<p>这种表示方式带来的优点如下: </p>
<ol>
<li>无需修改就可以直接使用标准的<code>二叉查找树</code>中的查找方法(其他与链接颜色不关联的方法也可以直接使用).</li>
</ol>
<ol start="2">
<li>对于任意的<code>2-3树</code>,只要对节点进行转换,我们都可以立即派生出一棵对应的<code>二叉查找树</code>.</li>
</ol>
<h2 id="红黑树的性质"><a href="#红黑树的性质" class="headerlink" title="红黑树的性质"></a>红黑树的性质</h2><hr>
<p><code>红黑树</code>是含有红黑链接并满足下列条件的<code>二叉查找树</code>(满足这些条件的<code>红黑树</code>才是与相应的<code>2-3树</code>一一对应的).</p>
<ul>
<li>红链接均为左链接(这条仅限于偏向左红链接实现的<code>红黑树</code>).</li>
</ul>
<ul>
<li>每个节点不是红色就是黑色的.</li>
</ul>
<ul>
<li>没有任何一个节点同时和两条红链接相连(不可以有两条连续的红链接).</li>
</ul>
<ul>
<li>该树是完美黑色平衡的,即<strong>任意空链接到根节点的路径上的黑链接数量相同.</strong></li>
</ul>
<ul>
<li><code>根节点</code>是黑色的.</li>
</ul>
<ul>
<li>所有<code>叶子节点</code>(即null节点)的颜色是黑色的.</li>
</ul>
<h2 id="与2-3树的对应关系"><a href="#与2-3树的对应关系" class="headerlink" title="与2-3树的对应关系"></a>与2-3树的对应关系</h2><hr>
<p>假如我们将一棵<code>红黑树</code>中的红链接画平,我们会发现所有的空链接到根节点的距离都将是相同的.如果再把由红链接相连的节点合并,得到的就是一棵<code>2-3树</code>.</p>
<p>相对的,如果将一棵<code>2-3树</code>中的<code>3-节点</code>画作由红色左链接相连的两个<code>2-节点</code>,那么不会存在能够和两条红链接相连的节点,且树必然是完美黑色平衡的,因为黑链接就是<code>2-3树</code>中的普通链接,根据定义这些链接必然是完美平衡的.</p>
<p>通过这些结论,我们<strong>可以发现<code>红黑树</code>即是<code>二叉查找树</code>,也是<code>2-3树</code>.</strong></p>
<p><img src="http://algs4.cs.princeton.edu/33balanced/images/redblack-1-1.png"></p>
<h2 id="节点的实现"><a href="#节点的实现" class="headerlink" title="节点的实现"></a>节点的实现</h2><hr>
<p>我们使用<code>boolean</code>类型的变量<code>color</code>来表示链接的颜色.如果指向它的链接为红色,则<code>color</code>变量为<code>true</code>,黑色则为<code>false</code>(空链接也为黑色).</p>
<p>并且定义了一个<code>isRed()</code>函数用于判断链接的颜色.</p>
<p>这里节点的<strong>颜色指的是指向该节点的链接的颜色.</strong></p>
<p><img src="http://algs4.cs.princeton.edu/33balanced/images/redblack-color.png"></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line">  <span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">boolean</span> RED = <span class="keyword">true</span>;</span><br><span class="line">  <span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">boolean</span> BLACK = <span class="keyword">false</span>;</span><br><span class="line"></span><br><span class="line">  <span class="keyword">private</span> Node root; <span class="comment">// root node</span></span><br><span class="line"></span><br><span class="line">  <span class="keyword">private</span> <span class="class"><span class="keyword">class</span> <span class="title">Node</span> </span>&#123;</span><br><span class="line">      <span class="keyword">private</span> K key;</span><br><span class="line">      <span class="keyword">private</span> V value;</span><br><span class="line">      <span class="keyword">private</span> Node left, right; <span class="comment">// links to left and right subtress</span></span><br><span class="line">      <span class="keyword">private</span> <span class="keyword">boolean</span> color; <span class="comment">// color of parent link</span></span><br><span class="line">      <span class="keyword">private</span> <span class="keyword">int</span> size; <span class="comment">// subtree count</span></span><br><span class="line"></span><br><span class="line">      <span class="function"><span class="keyword">public</span> <span class="title">Node</span><span class="params">(K key, V value, <span class="keyword">boolean</span> color, <span class="keyword">int</span> size)</span> </span>&#123;</span><br><span class="line">          <span class="keyword">this</span>.key = key;</span><br><span class="line">          <span class="keyword">this</span>.value = value;</span><br><span class="line">          <span class="keyword">this</span>.color = color;</span><br><span class="line">          <span class="keyword">this</span>.size = size;</span><br><span class="line">      &#125;</span><br><span class="line">  &#125;</span><br><span class="line">	</span><br><span class="line"><span class="comment">// node x is red? if x is null return false.</span></span><br><span class="line">  <span class="function"><span class="keyword">private</span> <span class="keyword">boolean</span> <span class="title">isRed</span><span class="params">(Node x)</span> </span>&#123;</span><br><span class="line">      <span class="keyword">if</span> (x == <span class="keyword">null</span>) <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">      <span class="keyword">return</span> x.color == RED;</span><br><span class="line">  &#125;</span><br></pre></td></tr></table></figure>
<h2 id="旋转"><a href="#旋转" class="headerlink" title="旋转"></a>旋转</h2><hr>
<p>当我们在实现某些操作时,可能会产生一些红色右链接或者两条连续的红色左链接.这时就需要在操作完成前进行旋转操作来修复<code>红黑树</code>的平衡性(<strong>旋转操作会改变红链接的指向</strong>).</p>
<p>旋转操作保证了<code>红黑树</code>的两个重要性质 : <strong>有序性</strong>和<strong>完美平衡性</strong>. </p>
<h4 id="左旋转"><a href="#左旋转" class="headerlink" title="左旋转"></a>左旋转</h4><p>假设当前有一条红色右链接需要被修正旋转为左链接.这个操作叫做<code>左旋转</code>.</p>
<p><code>左旋转</code>函数接受一条指向<code>红黑树</code>中的某个节点的链接作为参数.然后<strong>会对树进行必要的调整并返回一个指向包含同一组键的子树且其左链接为红色的根节点的链接.</strong></p>
<p>也可以认为是<strong>将用两个键中的较小者作为根节点变为将较大者作为根节点</strong>(右旋转中逻辑相反).</p>
<p>旋转操作返回的链接可能是左链接也可能是右链接,这个链接可能是红色也可能是黑色的(在实现中我们使用<code>x.color = h.color</code>保留了它原本的颜色).这<strong>可能会产生两条连续的红链接,但算法会在后续操作中继续使用旋转操作修正这种情况.</strong></p>
<p><strong>旋转操作只影响了根节点</strong>(返回的节点的子树中的所有键和旋转前都相同,只有根节点发生了变化).</p>
<p>具体的实现如下图: </p>
<p><img src="http://algs4.cs.princeton.edu/33balanced/images/redblack-left-rotate.png"></p>
<h4 id="右旋转"><a href="#右旋转" class="headerlink" title="右旋转"></a>右旋转</h4><p>实现<code>右旋转</code>的逻辑基本与<code>左旋转</code>相同,只需要将<code>left</code>和<code>right</code>互换即可.</p>
<p><img src="http://algs4.cs.princeton.edu/33balanced/images/redblack-right-rotate.png"></p>
<h2 id="颜色转换"><a href="#颜色转换" class="headerlink" title="颜色转换"></a>颜色转换</h2><hr>
<p>颜色转换操作也是用于保证<code>红黑树</code>的性质的.<strong>它将<code>父节点</code>的颜色由黑变红,将<code>子节点</code>的颜色由红变黑.</strong></p>
<p>这项操作与旋转操作一样是局部变换,<strong>不会影响整棵树的黑色平衡性.</strong></p>
<p><img src="http://algs4.cs.princeton.edu/33balanced/images/color-flip.png"></p>
<h4 id="根节点总是为黑"><a href="#根节点总是为黑" class="headerlink" title="根节点总是为黑"></a>根节点总是为黑</h4><p>颜色转换可能会使<code>根节点</code>变为红色,但红色的<code>根节点</code>说明<code>根节点</code>是一个<code>3-节点</code>的一部分,实际情况并不是这样的.所以我们需要将<code>根节点</code>设为黑色.</p>
<p><strong>每当<code>根节点</code>由红变黑时,树的黑链接高度就会加1.</strong></p>
<h2 id="插入"><a href="#插入" class="headerlink" title="插入"></a>插入</h2><hr>
<p>在<code>红黑树</code>中实现插入操作是比较复杂的,因为需要保持<code>红黑树</code>的平衡性.但只要利用好<code>左旋转</code>、<code>右旋转</code>、<code>颜色转换</code>这三个辅助操作,就能够保证插入操作后树的平衡性.</p>
<h4 id="向单个2-节点中插入新键"><a href="#向单个2-节点中插入新键" class="headerlink" title="向单个2-节点中插入新键"></a>向单个2-节点中插入新键</h4><p>当一棵只含有一个键的<code>红黑树</code>只含有一个<code>2-节点</code>时,插入另一个键后需要马上进行<code>旋转</code>操作修正树的平衡性.</p>
<ul>
<li>如果新键小于老键,只需要新增一个红色的节点即可(这时,新的<code>红黑树</code>等价于一个<code>3-节点</code>).</li>
</ul>
<ul>
<li>如果新键大于老键,那么新增的红色节点将会产生一条红色的右链接,这时就需要使用<code>左旋转</code>修正根节点的链接.</li>
</ul>
<ul>
<li>以上两种情况最终的结果均为一棵等价于单个<code>3-节点</code>的<code>红黑树</code>,它含有两个键,一条红链接,树的黑链接高度为1.</li>
</ul>
<h4 id="向树底部的2-节点插入新键"><a href="#向树底部的2-节点插入新键" class="headerlink" title="向树底部的2-节点插入新键"></a>向树底部的2-节点插入新键</h4><p>和<code>二叉查找树</code>一样,向<code>红黑树</code>中插入一个新键会在树的底部新增一个节点,但<strong>在<code>红黑树</code>中总是用红链接将新节点和它的父节点相连.</strong></p>
<p>如果它的父节点是一个<code>2-节点</code>,那么上一节讨论的方法依然适用.</p>
<ul>
<li>如果指向新节点的是父节点的左链接,那么父节点就直接成为一个<code>3-节点</code>.</li>
</ul>
<ul>
<li>如果指向新节点的是父节点的右链接,那么就需要一次<code>左旋转</code>进行修正.</li>
</ul>
<h4 id="向一棵双键树-一个3-节点-中插入新键"><a href="#向一棵双键树-一个3-节点-中插入新键" class="headerlink" title="向一棵双键树(一个3-节点)中插入新键"></a>向一棵双键树(一个3-节点)中插入新键</h4><p>当向一个<code>3-节点</code>中插入新键时,会发生以下三种情况且每种情况都会产生一个同时连接到两条红链接的节点,我们需要修正这一点.</p>
<ul>
<li>如果<code>新键大于原树中的两个键</code> : 这是最容易处理的一种情况,这个<strong>键会被连接到<code>3-节点</code>的右链接</strong>.此时树是平衡的,<strong>根节点为中间大小的键</strong>,它有<strong>两条红链接分别和较小和较大的节点相连</strong>.只需要<strong>把这两条链接的颜色都由红变黑,那么就可以得到一棵由三个节点组成、高度为2的平衡树</strong>(其他两种情况最终也会转化为这样的树).</li>
</ul>
<ul>
<li>如果<code>新键小于原树中的两个键</code> : 这个<strong>键会被连接到最左边的空链接,这样就产生了两条连续的红链接.**此时</strong>只需要将上层的红链接<code>右旋转</code>即可得到第一种情况**(中值键为根节点并和其他两个节点用红链接相连).</li>
</ul>
<ul>
<li>如果<code>新键介于原树中的两个键之间</code> : 这种情况依然<strong>会产生两条连续的红链接:一条红色左链接接一条红色右链接.**此时</strong>只需要将下层的红链接<code>左旋转</code>即可得到第二种情况**(两条连续的红色左链接).</li>
</ul>
<p>通过以上这三种情况可以总结出 : 我们只需要通过0次、1次、2次旋转以及颜色转换就可以完成对<code>红黑树</code>的修正.</p>
<h4 id="将红链接向上传递"><a href="#将红链接向上传递" class="headerlink" title="将红链接向上传递"></a>将红链接向上传递</h4><p>当每次旋转操作之后都会进行<code>颜色转换</code>,它会使得中间节点变为红色.<strong>从父节点的角度来看,处理这样一个红色节点的方式和处理一个新插入的红色节点完全相同</strong>(继续将红链接转移到中间节点).</p>
<p>这个操作对应于<code>2-3树</code>中向<code>3-节点</code>进行插入的操作 : 即在一个<code>3-节点</code>下插入新键,需要创建一个临时的<code>4-节点</code>,将其分解并将中间键插入父节点(在<code>红黑树</code>中,是将红链接由中间键传递给它的父节点).重复这个过程,直至遇到一个<code>2-节点</code>或者根节点.</p>
<p>当根节点变为红色时需要将根节点的颜色转换为黑色(对应<code>2-3树</code>中的根节点分解).</p>
<h4 id="实现"><a href="#实现" class="headerlink" title="实现"></a>实现</h4><p>插入操作的实现除了每次递归调用之后的对平衡性修正的操作,其他与<code>二叉查找树</code>中的插入操作没什么不同.</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">put</span><span class="params">(K key, V val)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (key == <span class="keyword">null</span>) <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;first argument to put() is null&quot;</span>);</span><br><span class="line">    <span class="keyword">if</span> (val == <span class="keyword">null</span>) &#123;</span><br><span class="line">        delete(key);</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    root = put(root, key, val);</span><br><span class="line">    root.color = BLACK;</span><br><span class="line">    <span class="function"><span class="keyword">assert</span> <span class="title">check</span><span class="params">()</span></span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// insert the key-value pair in the subtree rooted at h</span></span><br><span class="line"><span class="function"><span class="keyword">private</span> Node <span class="title">put</span><span class="params">(Node h, K key, V val)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (h == <span class="keyword">null</span>) <span class="keyword">return</span> <span class="keyword">new</span> Node(key, val, RED, <span class="number">1</span>);</span><br><span class="line"></span><br><span class="line">    <span class="keyword">int</span> cmp = key.compareTo(h.key);</span><br><span class="line">    <span class="keyword">if</span> (cmp &lt; <span class="number">0</span>) h.left = put(h.left, key, val);</span><br><span class="line">    <span class="keyword">else</span> <span class="keyword">if</span> (cmp &gt; <span class="number">0</span>) h.right = put(h.right, key, val);</span><br><span class="line">    <span class="keyword">else</span> h.value = val;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// fix-up any right-leaning links</span></span><br><span class="line">    <span class="keyword">if</span> (isRed(h.right) &amp;&amp; !isRed(h.left)) h = rotateLeft(h);</span><br><span class="line">    <span class="keyword">if</span> (isRed(h.left) &amp;&amp; isRed(h.left.left)) h = rotateRight(h);</span><br><span class="line">    <span class="keyword">if</span> (isRed(h.left) &amp;&amp; isRed(h.right)) flipColors(h);</span><br><span class="line">    h.size = size(h.left) + size(h.right) + <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> h;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h4><p>只要在沿着插入点到根节点的路径向上移动时<strong>在所经过的每个节点中顺序完成以下操作</strong>,就能够实现<code>红黑树</code>的插入操作.</p>
<ul>
<li>如果<code>右子节点</code>是红色的而<code>左子节点</code>是黑色的,那么进行<code>左旋转</code>.</li>
</ul>
<ul>
<li>如果<code>左子节点</code>是红色的而且它的<code>左子节点</code>也是红色的,那么进行<code>右旋转</code>.</li>
</ul>
<ul>
<li>如果<code>左右子节点</code>都是红色的,那么进行<code>颜色转换</code>.</li>
</ul>
<h2 id="删除"><a href="#删除" class="headerlink" title="删除"></a>删除</h2><hr>
<p>删除操作也需要定义一系列<code>局部变换</code>来在<strong>删除一个节点的同时保持树的完美平衡性</strong>.然而,这个过程要比插入操作还要复杂,它<strong>不仅要在(为了删除一个节点而)构造临时<code>4-节点</code>时沿着查找路径向下进行变换,还要在分解遗留的<code>4-节点</code>时沿着查找路径向上进行变换(同插入操作)</strong>.</p>
<h4 id="自顶向下的2-3-4树"><a href="#自顶向下的2-3-4树" class="headerlink" title="自顶向下的2-3-4树"></a>自顶向下的2-3-4树</h4><p><code>2-3-4树</code>是一种允许存在<code>4-节点</code>的树.它的插入算法就是一种沿着查找路径既能向上也能向下进行变换的算法.</p>
<ul>
<li>沿查找路径向下进行变换(向下变换与<code>2-3树</code>中分解<code>4-节点</code>所进行的变换完全相同)是为了保证当前节点不是<code>4-节点</code>(这样树的底部才有足够的空间插入新的键).</li>
</ul>
<ul>
<li>沿查找路径向上进行变换是为了将之前创建的<code>4-节点</code>配平.</li>
</ul>
<ul>
<li>如果<code>根节点</code>是一个<code>4-节点</code>,就将它分解成三个<code>2-节点</code>,树的高度加1.</li>
</ul>
<ul>
<li>如果在向下查找的过程中,遇到了一个<code>父节点</code>为<code>2-节点</code>的<code>4-节点</code>,就将<code>4-节点</code>分解为两个<code>2-节点</code>并将<code>中间键</code>传递给它的<code>父节点</code>(这时<code>父节点</code>变为了一个<code>3-节点</code>).</li>
</ul>
<ul>
<li>如果遇到了一个<code>父节点</code>为<code>3-节点</code>的<code>4-节点</code>,将<code>4-节点</code>分解为两个<code>2-节点</code>并将<code>中间键</code>传递给它的<code>父节点</code>(这时<code>父节点</code>变为了一个<code>4-节点</code>).</li>
</ul>
<ul>
<li>不必担心遇见<code>父节点</code>为<code>4-节点</code>的<code>4-节点</code>,算法本身保证了不会出现这种情况,到达树的底部之后,只会遇到<code>2-节点</code>或者<code>3-节点</code>.</li>
</ul>
<p>如果要使用<code>红黑树</code>来实现这个算法,需要以下步骤 : </p>
<ul>
<li>将<code>4-节点</code>表示为由三个<code>2-节点</code>组成的一棵平衡的子树,<code>根节点</code>和两个子节点都用红链接相连.</li>
</ul>
<ul>
<li>在向下的过程中分解所有<code>4-节点</code>并进行<code>颜色转换</code>.</li>
</ul>
<ul>
<li>在向上的过程中使用<code>旋转</code>将<code>4-节点</code>配平.</li>
</ul>
<p>只需要将插入一节中的<code>put()</code>实现方法里的<code>flipColors</code>语句(及其if语句)移动到递归调用之前(null判断和比较操作之间)就能实现<code>2-3-4树</code>的插入操作.</p>
<h4 id="删除最小键"><a href="#删除最小键" class="headerlink" title="删除最小键"></a>删除最小键</h4><p>从<code>2-节点</code>中删除一个键会留下一个空节点,一般会将它替换为一个空链接,但这样会破坏树的完美平衡性.所以在删除操作中,<strong>为了避免删除一个<code>2-节点</code>,我们沿着<code>左链接</code>向下进行变换时,需要确保当前节点不是<code>2-节点</code></strong>.</p>
<p><code>根节点</code>可能有以下两种情况:</p>
<ol>
<li>如果<code>根节点</code>是一个<code>2-节点</code>且它的两个子节点都是<code>2-节点</code>,可以直接将这三个节点变成一个<code>4-节点</code>.</li>
</ol>
<ol start="2">
<li>否则,需要保证<code>根节点</code>的左子节点不是<code>2-节点</code>,必要时可以从它右侧的兄弟节点借走一个键.</li>
</ol>
<p>在沿着<code>左链接</code>向下的过程中,保证以下情况之一成立: </p>
<ul>
<li>如果当前节点的左子节点不是<code>2-节点</code>.</li>
</ul>
<ul>
<li>如果当前节点的左子节点是<code>2-节点</code>而它的兄弟节点不是<code>2-节点</code>,将左子节点的兄弟节点中的一个键移动到左子节点中</li>
</ul>
<ul>
<li>如果当前节点的左子节点和它的兄弟节点都是<code>2-节点</code>,将左子节点、父节点中的最小键和左子节点最近的兄弟节点合并为一个<code>4-节点</code>,使父节点由<code>3-节点</code>变为<code>2-节点</code>(或是从<code>4-节点</code>变为<code>3-节点</code>).</li>
</ul>
<p>只要保证了以上的条件,我们最终能够得到一个含有最小键的<code>3-节点</code>或<code>4-节点</code>(然后进行删除即可),之后再不断向上分解所有临时的<code>4-节点</code>.</p>
<h5 id="代码实现"><a href="#代码实现" class="headerlink" title="代码实现"></a>代码实现</h5><p>在删除操作中,<code>颜色转换</code>的操作与插入操作中的实现略微有些不同(需要将父节点设为黑,而将两个子节点设为红).</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">flipColors</span><span class="params">(Node h)</span> </span>&#123;</span><br><span class="line">       h.color = !h.color;</span><br><span class="line">       h.left.color = !h.left.color;</span><br><span class="line">       h.right.color = !h.right.color;</span><br><span class="line">   &#125;</span><br><span class="line"></span><br><span class="line">   <span class="comment">// restore red-black tree invariant</span></span><br><span class="line">   <span class="function"><span class="keyword">private</span> Node <span class="title">balance</span><span class="params">(Node h)</span> </span>&#123;</span><br><span class="line">       <span class="keyword">if</span> (isRed(h.right)) h = rotateLeft(h);</span><br><span class="line">       <span class="keyword">if</span> (isRed(h.left) &amp;&amp; isRed(h.left.left)) h = rotateRight(h);</span><br><span class="line">       <span class="keyword">if</span> (isRed(h.left) &amp;&amp; isRed(h.right)) flipColors(h);</span><br><span class="line"></span><br><span class="line">       h.size = size(h.left) + size(h.right) + <span class="number">1</span>;</span><br><span class="line">       <span class="keyword">return</span> h;</span><br><span class="line">   &#125;</span><br><span class="line"></span><br><span class="line">   <span class="comment">// Assuming that h is red and both h.left and h.left.left</span></span><br><span class="line">   <span class="comment">// are black, make h.left or one of its children red.</span></span><br><span class="line">   <span class="function"><span class="keyword">private</span> Node <span class="title">moveRedLeft</span><span class="params">(Node h)</span> </span>&#123;</span><br><span class="line">       flipColors(h);</span><br><span class="line">       <span class="keyword">if</span> (isRed(h.right.left)) &#123;</span><br><span class="line">           h.right = rotateRight(h.right);</span><br><span class="line">           h = rotateLeft(h);</span><br><span class="line">           flipColors(h);</span><br><span class="line">       &#125;</span><br><span class="line">       <span class="keyword">return</span> h;</span><br><span class="line">   &#125;</span><br><span class="line"></span><br><span class="line">   <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">deleteMin</span><span class="params">()</span> </span>&#123;</span><br><span class="line">       <span class="keyword">if</span> (isEmpty()) <span class="keyword">throw</span> <span class="keyword">new</span> NoSuchElementException(<span class="string">&quot;RedBlackBST underflow.&quot;</span>);</span><br><span class="line"></span><br><span class="line">       <span class="comment">// if both children of root are black, set root to red</span></span><br><span class="line">       <span class="keyword">if</span> (!isRed(root.left) &amp;&amp; !isRed(root.right))</span><br><span class="line">           root.color = RED;</span><br><span class="line"></span><br><span class="line">       root = deleteMin(root);</span><br><span class="line">       <span class="keyword">if</span> (!isEmpty())</span><br><span class="line">           root.color = BLACK;</span><br><span class="line">   &#125;</span><br><span class="line"></span><br><span class="line">   <span class="comment">// delete the key-value pair with the minimum key rooted at h</span></span><br><span class="line">   <span class="function"><span class="keyword">private</span> Node <span class="title">deleteMin</span><span class="params">(Node h)</span> </span>&#123;</span><br><span class="line">       <span class="keyword">if</span> (h.left == <span class="keyword">null</span>)</span><br><span class="line">           <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line">       <span class="keyword">if</span> (!isRed(h.left) &amp;&amp; !isRed(h.left.left))</span><br><span class="line">           h = moveRedLeft(h);</span><br><span class="line"></span><br><span class="line">       h.left = deleteMin(h.left);</span><br><span class="line">       <span class="keyword">return</span> balance(h);</span><br><span class="line">   &#125;	</span><br></pre></td></tr></table></figure>
<h4 id="删除最大键"><a href="#删除最大键" class="headerlink" title="删除最大键"></a>删除最大键</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// Assuming that h is red and both h.right and h.right.left</span></span><br><span class="line"><span class="comment">// are black, make h.right or one of its children red.</span></span><br><span class="line"><span class="function"><span class="keyword">private</span> Node <span class="title">moveRedRight</span><span class="params">(Node h)</span> </span>&#123;</span><br><span class="line">    flipColors(h);</span><br><span class="line">    <span class="keyword">if</span> (isRed(h.left.left)) &#123;</span><br><span class="line">        h = rotateRight(h);</span><br><span class="line">        flipColors(h);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> h;</span><br><span class="line">&#125;</span><br><span class="line">	</span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">deleteMax</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (isEmpty()) <span class="keyword">throw</span> <span class="keyword">new</span> NoSuchElementException(<span class="string">&quot;RedBlackBST underflow.&quot;</span>);</span><br><span class="line"></span><br><span class="line">    <span class="comment">// if both children of root are black, set root to red</span></span><br><span class="line">    <span class="keyword">if</span> (!isRed(root.left) &amp;&amp; !isRed(root.right))</span><br><span class="line">        root.color = RED;</span><br><span class="line"></span><br><span class="line">    root = deleteMax(root);</span><br><span class="line">    <span class="keyword">if</span> (!isEmpty())</span><br><span class="line">        root.color = BLACK;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// delete the key-value pair with the maximum key rooted at h</span></span><br><span class="line"><span class="function"><span class="keyword">private</span> Node <span class="title">deleteMax</span><span class="params">(Node h)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (isRed(h.left))</span><br><span class="line">        h = rotateRight(h);</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> (h.right == <span class="keyword">null</span>)</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> (!isRed(h.right) &amp;&amp; !isRed(h.right.left))</span><br><span class="line">        h = moveRedRight(h);</span><br><span class="line"></span><br><span class="line">    h.right = deleteMax(h.right);</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> balance(h);</span><br><span class="line">&#125;	</span><br></pre></td></tr></table></figure>
<h4 id="删除操作"><a href="#删除操作" class="headerlink" title="删除操作"></a>删除操作</h4><p>同样也需要像删除最小键那样在查找路径上进行变换来保证查找过程中任意当前节点均不是<code>2-节点</code>.如果目标键在树的底部,可以直接删除它;如果不在,则需要将它和它的后继节点交换.</p>
<p>在删除操作之后需要向上变换分解余下的<code>4-节点</code>.</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">delete</span><span class="params">(K key)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (key == <span class="keyword">null</span>) <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;called delete() with key is null.&quot;</span>);</span><br><span class="line">    <span class="keyword">if</span> (!contains(key)) <span class="keyword">return</span>;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// if both children of root are black, set root to red</span></span><br><span class="line">    <span class="keyword">if</span> (!isRed(root.left) &amp;&amp; !isRed(root.right))</span><br><span class="line">        root.color = RED;</span><br><span class="line"></span><br><span class="line">    root = delete(root, key);</span><br><span class="line">    <span class="keyword">if</span> (!isEmpty()) root.color = BLACK;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// delete the key-value pair with the given key rooted at h</span></span><br><span class="line"><span class="function"><span class="keyword">private</span> Node <span class="title">delete</span><span class="params">(Node h, K key)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (key.compareTo(h.key) &lt; <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">if</span> (!isRed(h.left) &amp;&amp; !isRed(h.left.left))</span><br><span class="line">            h = moveRedLeft(h);</span><br><span class="line">        h.left = delete(h.left, key);</span><br><span class="line">    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">        <span class="keyword">if</span> (isRed(h.left))</span><br><span class="line">            h = rotateRight(h);</span><br><span class="line">        <span class="keyword">if</span> (key.compareTo(h.key) == <span class="number">0</span> &amp;&amp; (h.right == <span class="keyword">null</span>))</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">        <span class="keyword">if</span> (!isRed(h.right) &amp;&amp; !isRed(h.right.left))</span><br><span class="line">            h = moveRedRight(h);</span><br><span class="line">        <span class="keyword">if</span> (key.compareTo(h.key) == <span class="number">0</span>) &#123;</span><br><span class="line">            Node x = min(h.right);</span><br><span class="line">            h.key = x.key;</span><br><span class="line">            h.value = x.value;</span><br><span class="line">            h.right = deleteMin(h.right);</span><br><span class="line">        &#125; <span class="keyword">else</span> h.right = delete(h.right, key);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> balance(h);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="总结-1"><a href="#总结-1" class="headerlink" title="总结"></a>总结</h2><hr>
<p>无论键的插入顺序如何,<code>红黑树</code>都几乎是完美平衡的,基于它实现的有序符号表操作的运行时间均为对数级别(除了范围查询).</p>
<p>在<code>红黑树</code>的实现中复杂的代码仅限于<code>put()</code>和<code>delete()</code>方法,像<code>get()</code>这些不会涉及检查颜色的方法与<code>二叉查找树</code>中的实现一致(因为这些操作与平衡性无关).</p>
<h2 id="end"><a href="#end" class="headerlink" title="end"></a>end</h2><hr>
<ul>
<li>Author : <a target="_blank" rel="noopener" href="https://github.com/SylvanasSun">SylvanasSun</a></li>
</ul>
<ul>
<li>Email : <a href="mailto:&#115;&#121;&#108;&#x76;&#x61;&#x6e;&#97;&#115;&#115;&#x75;&#110;&#x5f;&#x78;&#x74;&#122;&#x40;&#49;&#x36;&#51;&#x2e;&#x63;&#x6f;&#109;">&#115;&#121;&#108;&#x76;&#x61;&#x6e;&#97;&#115;&#115;&#x75;&#110;&#x5f;&#x78;&#x74;&#122;&#x40;&#49;&#x36;&#51;&#x2e;&#x63;&#x6f;&#109;</a></li>
</ul>
<ul>
<li>文中的完整实现代码见我的<a target="_blank" rel="noopener" href="https://github.com/SylvanasSun/algs4-study">GitHub</a> &amp; <a target="_blank" rel="noopener" href="https://gist.github.com/SylvanasSun/731a1438c61492628cfaa1e9e618ecfb">Gist</a></li>
</ul>
<ul>
<li>本文参考资料引用自<a target="_blank" rel="noopener" href="http://algs4.cs.princeton.edu/33balanced/">《Algorithms,4th Editio》</a></li>
</ul>

    </div>

    
    
    

    <footer class="post-footer">
          <div class="post-tags">
              <a href="/yuwanzi.io/tags/2017/" rel="tag"># 2017</a>
              <a href="/yuwanzi.io/tags/Algorithms/" rel="tag"># Algorithms</a>
              <a href="/yuwanzi.io/tags/Tree/" rel="tag"># Tree</a>
              <a href="/yuwanzi.io/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" rel="tag"># 数据结构</a>
          </div>

        

          <div class="post-nav">
            <div class="post-nav-item">
                <a href="/yuwanzi.io/2017/03/28/2017-3-28-2_3tree/" rel="prev" title="《Algorithms,4th Edition》读书笔记-2-3查找树">
                  <i class="fa fa-chevron-left"></i> 《Algorithms,4th Edition》读书笔记-2-3查找树
                </a>
            </div>
            <div class="post-nav-item">
                <a href="/yuwanzi.io/2017/04/08/2017-4-08-avl_tree/" rel="next" title="平衡查找树之AVL树">
                  平衡查找树之AVL树 <i class="fa fa-chevron-right"></i>
                </a>
            </div>
          </div>
    </footer>
  </article>
</div>







<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      const activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      const commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>
</div>
  </main>

  <footer class="footer">
    <div class="footer-inner">


<div class="copyright">
  &copy; 
  <span itemprop="copyrightYear">2021</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">玉丸子</span>
</div>
  <div class="powered-by">Erstellt mit  <a href="https://hexo.io/" class="theme-link" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.js.org/muse/" class="theme-link" rel="noopener" target="_blank">NexT.Muse</a>
  </div>

    </div>
  </footer>

  
  <script src="//cdn.jsdelivr.net/npm/animejs@3.2.1/lib/anime.min.js"></script>
<script src="/yuwanzi.io/js/utils.js"></script><script src="/yuwanzi.io/js/motion.js"></script><script src="/yuwanzi.io/js/schemes/muse.js"></script><script src="/yuwanzi.io/js/next-boot.js"></script>

  






  





</body>
</html>
